#! /bin/bash
#

#=================================================================#
#  汉诺塔是由Edouard Lucas提出的数学谜题 ,
#+ 他是19世纪的法国数学家.
#
#  有三个直立的柱子竖在地面上.
#  第一个柱子有一组的盘子套在上面.
#  这些盘子是平整的，中间带着孔，
#+ 因此它们才能套在柱子上面.
#  这组盘子有不同的直径，它们是依照直径从小到大来从高到低放置.
#
#  最小的盘在最高，最大的盘在最底部.
#
#  现在的任务是要把这一组的盘子从一个柱子全部地搬到另一个柱子上.
#
#  你只能一次从一个柱子上移动一个盘子到另一个柱子.
#  允许把盘子重新移回到它原来的最初位置.
#  你可以把一个小的盘子放在大的盘子上面,
#+ 但不能把大的盘子放在小的盘子上面.
#  请注意这一点.
#
#  对于这一组盘子，数量少时，只需要移动很少的次数就能达到要求.
#+ 但随着这组盘子的数量的增加,
#+ 移动的次数几乎成倍增长的,
#+ 而移动的策略变得愈加复杂.
#
#  想了解更多的信息, 请访问 http://hanoi.kernelthread.com.
#
#
#         ...                   ...                    ...
#         | |                   | |                    | |
#        _|_|_                  | |                    | |
#       |_____|                 | |                    | |
#      |_______|                | |                    | |
#     |_________|               | |                    | |
#    |___________|              | |                    | |
#   |             |             | |                    | |
# .--------------------------------------------------------------.
# |**************************************************************|
#          #1                   #2                      #3
#
#=================================================================#


E_NOPARAM=66  # 没有参数传给脚本.
E_BADPARAM=67 # 传给脚本的盘子数不合法.
Moves=        # 保存移动次数的全局变量.
              # 这儿修改了原脚本.

dohanoi() {   # 递归函数.
    case $1 in
    0)
        ;;
    *)
        dohanoi "$(($1-1))" $2 $4 $3
        echo move $2 "-->" $3
   let "Moves += 1"  # 这儿修改了原脚本.
        dohanoi "$(($1-1))" $4 $3 $2
        ;;
    esac
}

case $# in
1)
    case $(($1>0)) in     # 至少要有一个盘子.
    1)
        dohanoi $1 1 3 2
        echo "Total moves = $Moves"
        exit 0;
        ;;
    *)
        echo "$0: illegal value for number of disks";
        exit $E_BADPARAM;
        ;;
    esac
    ;;
*)
    echo "usage: $0 N"
    echo "       Where \"N\" is the number of disks."
    exit $E_NOPARAM;
    ;;
esac

# 练习:
# ---------
# 1) 从现在这个位置以下的命令会不会总是被执行?
#    为什么? (容易)
# 2) 解释这个可运行的"dohanoi"函数的原理.
#    (难)